package Leetcode2.链表;

import test0ne.TreeNode;

import java.util.LinkedList;
import java.util.List;

public class 图 {

    private static List<List<Integer>> res = new LinkedList<>();

    //给定邻接矩阵，计算所有到n-1的可能路径
    private static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<Integer> path = new LinkedList<>();
        traverse(graph, 0, path);
        return res;
    }

    private static void traverse(int[][] graph, int s, List<Integer> path) {
        path.add(s);

        if(s == graph.length -1 ) {
            res.add(new LinkedList<>(path));
            path.remove(path.size()-1);
            return;
        }

        for (int i : graph[s]) {
            traverse(graph, i, path);
        }

        path.remove(path.size()-1);
    }

//    public static int maxSumBST(TreeNode root) {
//        //二叉树遍历框架， 前、中、后
//        //遍历每个节点的时候，要判断当前节点是干甚么
//        int max = Integer.MIN_VALUE;
//        getMaxSumBst(root, max);
//    }

//    private static void getMaxSumBst(TreeNode root, int max) {
//        //判断，左右子树是否的BST
//        //左边最大值小于当前值，当前值小于右边最小值
//        //
//    }

    //树的序列化和反序列化
    private static String NULL = "#";
    private static String SEP = ",";
    private static StringBuilder sb = new StringBuilder();

    public static String serialize(TreeNode root) {
        traverseFir(root);
        return sb.toString();
    }

    private static void traverseFir(TreeNode root) {
        if(root == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(root.val).append(SEP);
        traverseFir(root.left);
        traverseFir(root.right);
    }

    private static Integer index = 0;
    private static TreeNode deserialize(String str) {
        String[] strArr = str.split(SEP);
        return buildTree(strArr);
    }

    private static TreeNode buildTree(String[] strArr) {
        if(strArr[index].equals(NULL)) {
            index++;
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(strArr[index++]));
        root.left = buildTree(strArr);
        root.right = buildTree(strArr);
        return root;
    }


    public static void main(String[] args) {
        int[][] graph = {{1,2},{3},{3},{}};
        allPathsSourceTarget(graph);
        System.out.println(res.toString());

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.right = new TreeNode(4);
        System.out.println(serialize(root));

        TreeNode treeNode =  deserialize("1,2,#,4,#,#,3,#,#,");
        System.out.println(treeNode.toString());
    }
}
